package com.gxc.array;

/**
 * 3145. 大数组元素的乘积

 * 一个非负整数 x 的 强数组 指的是满足元素为 2 的幂且元素总和为 x 的最短有序数组。
 * 下表说明了如何确定 强数组 的示例。可以证明，x 对应的强数组是独一无二的。
 *
 * 数字	二进制表示	强数组
 * 1	00001	[1]
 * 8	01000	[8]
 * 10	01010	[2, 8]
 * 13	01101	[1, 4, 8]
 * 23	10111	[1, 2, 4, 16]
 *
 * 我们将每一个升序的正整数 i （即1，2，3等等）的 强数组 连接得到数组 big_nums ，
 * big_nums 开始部分为 [1, 2, 1, 2, 4, 1, 4, 2, 4, 1, 2, 4, 8, ...] 。
 *
 * 给你一个二维整数数组 queries ，其中 queries[i] = [fromi, toi, modi] ，
 * 你需要计算 (big_nums[fromi] * big_nums[fromi + 1] * ... * big_nums[toi]) % modi 。
 *
 * 请你返回一个整数数组 answer ，其中 answer[i] 是第 i 个查询的答案。
 */
public class FindProductsOfElements {

    public static void main(String[] args) {
        System.out.println(Long.numberOfTrailingZeros(1));
        System.out.println(Long.numberOfTrailingZeros(2));
        System.out.println(Long.numberOfTrailingZeros(9));
        System.out.println(3 << (3 - 1));
        System.out.println(4 << (4 - 1));

        System.out.println(sumE(10));
    }

    public static int[] handle(long[][] queries) {
        int[] ans = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            long[] q = queries[i];
            long er = sumE(q[1] + 1);
            long el = sumE(q[0]);
            //得到了幂次之和，可以用快速幂计算 2 的幂模 mod
            ans[i] = pow(2, er - el, q[2]);
        }
        return ans;
    }

    private static long sumE(long k) {
        long res = 0;
        long n = 0;
        long cnt1 = 0; // 之前填的 1 的个数
        long sumI = 0; // 之前填的 1 的幂次之和
        for (long i = 63 - Long.numberOfLeadingZeros(k + 1); i > 0; i--) {
            //i << (i - 1)   =  ones(2的i次)=i⋅2的（i−)次
            long c = (cnt1 << i) + (i << (i - 1)); // 新增的幂次个数
            if (c <= k) {
                k -= c;
                res += (sumI << i) + ((i * (i - 1) / 2) << (i - 1));
                sumI += i;
                cnt1++;
                n |= 1L << i; // 填 1
            }
        }
        // 最低位单独计算
        if (cnt1 <= k) {
            k -= cnt1;
            res += sumI;
            n |= 1; // 最低位填 1
        }
        // 剩余的 k 个幂次，由 n 的低 k 个 1 补充
        while (k-- > 0) {
            //Long.numberOfTrailingZeros(n) 最低位的1
            res += Long.numberOfTrailingZeros(n);
            //  n &= n - 1  去掉最低位的 1
            n &= n - 1; // 去掉最低位的 1（置为 0）
        }
        return res;
    }

    private static int pow(long x, long n, long mod) {
        long res = 1 % mod;
        for (; n > 0; n /= 2) {
            if (n % 2 == 1) {
                res = res * x % mod;
            }
            x = x * x % mod;
        }
        return (int) res;
    }

    class Solution {
        public int[] findProductsOfElements(long[][] queries) {
            int[] ans = new int[queries.length];

            for (int i = 0; i < queries.length; i++) {
                // 偏移让数组下标从1开始
                queries[i][0]++;
                queries[i][1]++;
                long l = midCheck(queries[i][0]);
                long r = midCheck(queries[i][1]);
                int mod = (int) queries[i][2];

                long res = 1;
                long pre = countOne(l - 1);
                for (int j = 0; j < 60; j++) {
                    if ((1L << j & l) != 0) {
                        pre++;
                        if (pre >= queries[i][0] && pre <= queries[i][1]) {
                            res = res * (1L << j) % mod;
                        }
                    }
                }

                if (r > l) {
                    long bac = countOne(r - 1);
                    for (int j = 0; j < 60; j++) {
                        if ((1L << j & r) != 0) {
                            bac++;
                            if (bac >= queries[i][0] && bac <= queries[i][1]) {
                                res = res * (1L << j) % mod;
                            }
                        }
                    }
                }

                if (r - l > 1) {
                    long xs = countPow(r - 1) - countPow(l);
                    res = res * powMod(2L, xs, mod) % mod;
                }
                ans[i] = (int) res;
            }

            return ans;
        }

        public long midCheck(long x) {
            long l = 1, r = (long) 1e15;
            while (l < r) {
                long mid = (l + r) >> 1;
                if (countOne(mid) >= x) {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            }
            return r;
        }

        // 计算 <= x 所有数的数位1的和
        public long countOne(long x) {
            long res = 0;
            int sum = 0;

            for (int i = 60; i >= 0; i--) {
                if ((1L << i & x) != 0) {
                    res += 1L * sum * (1L << i);
                    sum += 1;

                    if (i > 0) {
                        res += 1L * i * (1L << (i - 1));
                    }
                }
            }
            res += sum;
            return res;
        }

        // 计算 <= x 所有数的数位对幂的贡献之和
        public long countPow(long x) {
            long res = 0;
            int sum = 0;

            for (int i = 60; i >= 0; i--) {
                if ((1L << i & x) != 0) {
                    res += 1L * sum * (1L << i);
                    sum += i;

                    if (i > 0) {
                        res += 1L * i * (i - 1) / 2 * (1L << (i - 1));
                    }
                }
            }
            res += sum;
            return res;
        }

        public int powMod(long x, long y, int mod) {
            long res = 1;
            while (y != 0) {
                if ((y & 1) != 0) {
                    res = res * x % mod;
                }
                x = x * x % mod;
                y >>= 1;
            }
            return (int) res;
        }
    }

    class Solution2 {
        public int[] findProductsOfElements(long[][] queries) {
            int[] ans = new int[queries.length];
            for (int i = 0; i < queries.length; i++) {
                long[] q = queries[i];
                long er = sumE(q[1] + 1);
                long el = sumE(q[0]);
                //得到了幂次之和，可以用快速幂计算 2 的幂模 mod
                ans[i] = pow(2, er - el, q[2]);
            }
            return ans;
        }

        private long sumE(long k) {
            long res = 0;
            long n = 0;
            long cnt1 = 0; // 之前填的 1 的个数
            long sumI = 0; // 之前填的 1 的幂次之和
            for (long i = 63 - Long.numberOfLeadingZeros(k + 1); i > 0; i--) {
                //i << (i - 1)   =  ones(2的i次)=i⋅2的（i−)次
                long c = (cnt1 << i) + (i << (i - 1)); // 新增的幂次个数
                if (c <= k) {
                    k -= c;
                    res += (sumI << i) + ((i * (i - 1) / 2) << (i - 1));
                    sumI += i;
                    cnt1++;
                    n |= 1L << i; // 填 1
                }
            }
            // 最低位单独计算
            if (cnt1 <= k) {
                k -= cnt1;
                res += sumI;
                n |= 1; // 最低位填 1
            }
            // 剩余的 k 个幂次，由 n 的低 k 个 1 补充
            while (k-- > 0) {
                res += Long.numberOfTrailingZeros(n);
                n &= n - 1; // 去掉最低位的 1（置为 0）
            }
            return res;
        }

        private int pow(long x, long n, long mod) {
            long res = 1 % mod;
            for (; n > 0; n /= 2) {
                if (n % 2 == 1) {
                    res = res * x % mod;
                }
                x = x * x % mod;
            }
            return (int) res;
        }
    }

}
